package net.xuele.learn.leetcode.hot100;

import net.xuele.learn.leetcode.ListNode;
import org.junit.Test;

import java.util.*;

public class Practice {

    public int[] wtwoSumOrderly(int[] nums, int target) {
        if (nums == null) return null;
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum == target) {
                return new int[]{left + 1, right + 1};
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        return null;
    }


    public boolean judgeSquareSum(int c) {
        if (c < 0) return false;
        int i = 0;
        int j = (int) Math.sqrt(c);
        while (i <= j) {
            int sum = i * i + j * j;
            if (sum == c) {
                return true;
            } else if (sum < c) {
                i++;
            } else {
                j--;
            }
        }
        return false;
    }

    private final static HashSet<Character> vowels = new HashSet<>(
            Arrays.asList('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'));

    public String reverseVowels(String s) {
        if (s == null) {
            return null;
        }
        int i = 0, j = s.length() - 1;
        char[] result = new char[s.length()];
        while (i <= j) {
            char a = s.charAt(i);
            char b = s.charAt(j);
            if (!vowels.contains(a)) {
                result[i++] = a;
            } else if (!vowels.contains(b)) {
                result[j--] = b;
            } else {
                result[i++] = b;
                result[j--] = a;
            }
        }
        return new String(result);
    }


    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int l1 = m - 1;
        int l2 = n - 1;
        int len = m + n - 1;
        while (l1 >= 0 || l2 >= 0) {
            if (l1 < 0) {
                nums1[len--] = nums2[l2--];
            } else if (l2 < 0) {
                nums1[len--] = nums1[l1--];
            } else if (nums1[l1] > nums2[l2]) {
                nums1[len--] = nums1[l1--];
            } else {
                nums1[len--] = nums2[l2--];
            }
        }
    }


    public boolean hasCycle(ListNode head) {
        if (head == null) return false;

        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }

    public String findLongestWord(String s, List<String> d) {
        String result = "";
        for (String target : d) {
            int l1 = result.length();
            int l2 = target.length();
            if (l1 > l2 || (l1 == l2 && target.compareTo(result) < 0)) {
                continue;
            }
            if (isSub(s, target)) {
                result = target;
            }
        }


        return result;
    }


    boolean isSub(String s, String target) {
        int i = 0, j = 0;
        while (i < s.length() && j < target.length()) {
            if (s.charAt(i) == target.charAt(j)) {
                j++;
            }
            i++;
        }
        return j == s.length();
    }


    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int left = 0;
        int max = 0;
        for (int i = 0; i < s.length(); i++) {
            if (map.containsKey(s.charAt(i))) {
                left = Math.max(left, map.get(s.charAt(i)) + 1);
            }
            map.put(s.charAt(i), i);
            max = Math.max(max, i - left + 1);
        }


        return max;
    }


    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) {
            return "";
        }
        // 存在公共前缀，则拿第一个做基准去遍历即可
        String ans = strs[0];
        for (int i = 1; i < strs.length; i++) {
            int j = 0;
            for (; j < ans.length() && j < strs[i].length(); j++) {
                if (ans.charAt(j) != strs[i].charAt(j)) {
                    break;
                }
            }
            ans = ans.substring(0, j);
            // 说明不存在公共前缀
            if (ans.equals("")) {
                return ans;
            }
        }
        return ans;
    }

    @Test
    public void test() {
        String[] strs = new String[]{"c", "c"};
        System.out.println(longestCommonPrefix(strs));
    }

    /**
     * 换句话说，第一个字符串的排列之一是第二个字符串的子串
     * <p>
     * 执行耗时太长！！！
     *
     * @param s1
     * @param s2
     * @return
     */
    public boolean checkInclusion(String s1, String s2) {
        if (s1 == null || s1.length() == 0) {
            return false;
        }
        if (s2 == null || s2.length() == 0) {
            return false;
        }
        if (s2.indexOf(s1) > 0) {
            return true;
        }
        char[] chars = s1.toCharArray();
        Arrays.sort(chars);
        s1 = new String(chars);
        // 在s2上开辟这个长度的子串，再在这个子串上需找s1中的字段
        int length = s1.length();
        int i = 0;
        while (i + length <= s2.length()) {
            String sub = s2.substring(i, i + length);
            char[] subChars = sub.toCharArray();
            Arrays.sort(subChars);
            sub = new String(subChars);
            if (s1.equals(sub)) {
                return true;
            }
            i++;
        }

        return false;
    }


    @Test
    public void fun() {
        System.out.println(checkInclusion2("abcdxabcde"
                , "abcdeabcdx"));
    }


    public boolean checkInclusion1(String s1, String s2) {
        // 1 获取两个字符串的长度
        int s1_len = s1.length(), s2_len = s2.length();
        // 2 如果字符串1大于2，肯定不合法，返回false
        if (s1_len > s2_len) return false;
        // 3 存储两个字符串的各个字符数量
        int[] s1_ch = new int[26], s2_ch = new int[26];
        // 4 遍历字符串1。存储字符串1每一个字符数量、存储s2中与字符串1一样长度下的各个字符的数量
        for (int i = 0; i < s1_len; ++i) {
            ++s1_ch[s1.charAt(i) - 'a'];
            ++s2_ch[s2.charAt(i) - 'a'];
        }
        // 5 承接上面的，从s1_len的长度开始遍历至s2.length()
        for (int i = s1_len; i < s2_len; ++i) {
            // ！！！！重点：判断s1，s2当前区间里面是否各个字符的数量均一致！！！！
            if (isEqual(s1_ch, s2_ch)) return true;
            // 因为是滑动窗口，下面刚好滑过这个位置，所以--，
            --s2_ch[s2.charAt(i - s1_len) - 'a'];
            // 滑动到对当前位置的字符++
            ++s2_ch[s2.charAt(i) - 'a'];
        }
        return isEqual(s1_ch, s2_ch);
    }

    private boolean isEqual(int[] s1_ch, int[] s2_ch) {
        for (int i = 0; i < 26; ++i)
            if (s1_ch[i] != s2_ch[i])
                return false;
        return true;
    }

    /**
     * @param s1
     * @param s2
     * @return
     */
    Map<Character, Integer> need = new HashMap<>();
    Map<Character, Integer> window = new HashMap<>();

    /**
     * s2是否包含s1的排列
     * <p>
     * s2包含s1的排列，说明组成s1的字符可以随意组合，并且s2字符的相对顺序不能改变
     * 换句话说：就是看s2在s1长度的窗口中，组成s1的字符数和s2的相等
     *
     * @param s1
     * @param s2
     * @return
     */
    public boolean checkInclusion2(String s1, String s2) {
        int len1 = s1.length();
        int len2 = s2.length();
        int left = 0, right = 0, valid = 0;
        for (int i = 0; i < len1; i++) {
            char c = s1.charAt(i);
            // 统计s1中各个字符的个数
            need.put(c, need.getOrDefault(c, 0) + 1);
        }
        while (right < len2) {
            char r = s2.charAt(right);
            if (need.containsKey(r)) {
                // 辅助统计s2中与s1相同的字符的个数
                window.put(r, window.getOrDefault(r, 0) + 1);
                if (need.get(r).equals(window.get(r))) {
                    valid++;
                }
            }
            right++;
            // 判断左侧是否需要收缩
            // 这道题判断的是s2是否包含s1的排序，所以s2需要是连续的，
            // 也就是说窗口的大小是s1的长度，超过s1的长度窗口要收缩
            while (right - left >= len1) {
                if (valid == need.size()) {
                    return true;
                }
                char l = s2.charAt(left);
                // 收缩s2窗口时需要去掉多余的字符及其统计
                if (need.containsKey(l)) {
                    if (need.get(l).equals(window.get(l))) {
                        valid--;
                    }
                    window.put(l, window.get(l) - 1);
                }
                left++;
            }
        }
        return false;
    }


    public String multiply(String num1, String num2) {
        if ("0".equals(num1) || "0".equals(num2)) {
            return "0";
        }
        int len1 = num1.length();
        int len2 = num2.length();
        long l1 = 0, l2 = 0;
        for (int i = 0; i < num1.length(); i++) {
            l1 += (num1.charAt(i) - 48) * (long) Math.pow(10.0, len1 - 1);
            len1--;
        }

        for (int i = 0; i < num2.length(); i++) {
            l2 += (num2.charAt(i) - 48) * (long) Math.pow(10.0, len2 - 1);
            len2--;
        }
        long sum = l1 * l2;
        return String.valueOf(sum);
    }

    public ListNode sortList(ListNode head) {


        return mergeSort(head);
    }


    /**
     * 归并排序  todo
     * <p>
     * 另外一种解法见：net.xuele.learn.LeetCode#sortList(net.xuele.learn.leetcode.ListNode)
     * 1 1 1 1 1
     *
     * @param head
     * @return
     */
    private ListNode mergeSort(ListNode head) {
        // 如果没有结点/只有一个结点，无需排序，直接返回
        if (head == null || head.next == null) return head;
        // 快慢指针找出中位点
        ListNode slowp = head, fastp = head.next.next, l, r;
        // 即便是fastp.next.next == null，当fastp.next != null时，
        // 仍要继续走一步，典型就是链表的长度为奇数个的时候，
        // 仍要走一步保证slow达到中点位置

        while (fastp != null && fastp.next != null) {

            slowp = slowp.next;
            fastp = fastp.next.next;
        }
        // 对右半部分进行归并排序
        r = mergeSort(slowp.next);
        // 链表判断结束的标志：末尾节点.next==null
        slowp.next = null;
        // 对左半部分进行归并排序
        l = mergeSort(head);
        return mergeList(l, r);
    }

    /**
     * 合并链表 todo
     *
     * @param l
     * @param r
     * @return
     */
    private ListNode mergeList(ListNode l, ListNode r) {
        // 临时头节点
        ListNode tmpHead = new ListNode(-1);
        ListNode p = tmpHead;
        while (l != null && r != null) {
            if (l.val < r.val) {
                p.next = l;
                l = l.next;
            } else {
                p.next = r;
                r = r.next;
            }
            p = p.next;
        }
        p.next = l == null ? r : l;
        return tmpHead.next;
    }


    /**
     * 合并K个链表
     *
     * @param lists
     * @return
     */
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }
        ListNode listNode = lists[0];
        for (int i = 1; i < lists.length; i++) {

            ListNode l2 = lists[i];
            listNode = mergeTwoLists0(listNode, l2);
        }

        return listNode;
    }


    public void merge() {

    }


    private ListNode mergeTwoLists0(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }

        if (l1.val <= l2.val) {
            // 如果l1小于l2，那么第一个节点肯定是l1这个当前节点，
            // 然后再比较l1的下一个节点和l2
            l1.next = mergeTwoLists0(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists0(l2.next, l1);
            return l2;
        }
    }


    @Test
    public void funTest() {
        ListNode head1 = new ListNode(1);
        ListNode l2 = new ListNode(4);
        head1.next = l2;
        ListNode l3 = new ListNode(5);
        l2.next = l3;
        ListNode head2 = new ListNode(1);
        ListNode l4 = new ListNode(3);
        head2.next = l4;
        ListNode l5 = new ListNode(4);
        l4.next = l5;
        ListNode head3 = new ListNode(2);
        ListNode l6 = new ListNode(6);
        head3.next = l6;

        ListNode[] listNodes = new ListNode[]{head1, head2, head3};

        ListNode listNode = mergeKLists0(listNodes);
        System.out.println(listNode.val);
    }

    /**
     * 合并K个链表 todo
     *
     * @param lists
     * @return
     */
    public ListNode mergeKLists0(ListNode[] lists) {
        return mergeLists(lists, 0, lists.length - 1);
    }

    private ListNode mergeLists(ListNode[] lists, int start, int end) {
        if (start > end) {
            return null;
        } else if (start == end) {
            return lists[start];
        } else if (start + 1 == end) {
            return merge(lists[start], lists[end]);
        }

        int mid = start + (end - start) / 2;
        return merge(mergeLists(lists, start, mid), mergeLists(lists, mid + 1, end));
    }

    private ListNode merge(ListNode a, ListNode b) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        while (a != null && b != null) {
            if (a.val < b.val) {
                current.next = a;
                a = a.next;
            } else {
                current.next = b;
                b = b.next;
            }
            current = current.next;
        }

        current.next = a == null ? b : a;

        return dummy.next;
    }

    /**
     * 合并k个链表
     *
     * @param lists
     * @return
     */
    public ListNode mergeKLists1(ListNode[] lists) {
        // 递归终止
        if (lists.length == 0) {
            return null;
        }
        if (lists.length == 1) {
            return lists[0];
        }
        // 从中间划分为左右两部分
        int left = 0;
        int right = lists.length - 1;
        int mid = left + (right - left) / 2;
        ListNode[] left_lists = new ListNode[mid - left + 1];
        for (int i = left; i < mid + 1; i++) {
            left_lists[i] = lists[i];
        }
        ListNode[] right_lists = new ListNode[right - mid];
        for (int i = mid + 1; i < right + 1; i++) {
            right_lists[i - mid - 1] = lists[i];
        }
        // 分别将左右两部分合并得到链表
        ListNode left_node = mergeKLists1(left_lists);
        ListNode right_node = mergeKLists1(right_lists);
        // 合并左右两部分
        return mergeTwoLists(left_node, right_node);
    }

    /**
     * 合并两个排序链表，
     * 比如：1-> 4->7
     * 2->3->5
     *
     * @param L1
     * @param L2
     * @return
     */
    private ListNode mergeTwoLists(ListNode L1, ListNode L2) {
        // 合并两个链表
        ListNode head = new ListNode(0);
        ListNode pre = head;
        while (L1 != null && L2 != null) {
            if (L1.val < L2.val) {
                pre.next = L1;
                L1 = L1.next;
            } else {
                pre.next = L2;
                L2 = L2.next;
            }
            pre = pre.next;
        }
        if (L1 != null) {
            pre.next = L1;
        }
        if (L2 != null) {
            pre.next = L2;
        }
        return head.next;
    }


    /**
     * 674. 最长连续递增序列
     *
     * @param nums
     * @return
     */
    public int findLengthOfLCIS(int[] nums) {
        int max = 0;
        if (nums == null || nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return 1;
        }
        int j = 1, start = 0;
        while (j < nums.length) {
            int left = nums[j - 1];
            int right = nums[j];
            if (left < right) {
                j++;
            } else {
                start = j;
                j++;
            }
            max = Math.max(max, j - start);
        }
        return max;
    }


    /**
     * 128 最长连续序列
     *
     * @param nums
     * @return
     */
    public int longestConsecutive(int[] nums) {

        if (nums == null) {
            return 0;
        }
        int length = nums.length;
        if (length <= 1) {
            return length;
        }
        int max = 0;
        Arrays.sort(nums);
        int j = 1;
        for (int i = 1; i < length; i++) {
            if (nums[i] - nums[i - 1] == 1) {
                j++;
                max = Math.max(j, max);
            } else if (nums[i] - nums[i - 1] > 1) {
                j = 1;
            }
        }

        return Math.max(j, max);
    }

    @Test
    public void testFun() {
        int[] result = new int[]{1, 3, 5, 4, 7};
        int lengthOfLCIS = findLengthOfLCIS(result);
        System.out.println(lengthOfLCIS);
    }

}
